package two.recurtion;

import java.util.ArrayList;
import java.util.List;

/**
 * 子集：
 *      给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 *      解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 * 时间复杂度：O(2^n)
 * 思路：子集，递归（边界、本层逻辑、子问题、还原现场）
 */
public class Subsets {

    public List<List<Integer>> subsets(int[] nums){
        ans = new ArrayList<List<Integer>>();
        process = new ArrayList<Integer>();
        findSubsets(nums, 0);
        return ans;
    }

    private void findSubsets(int[] nums, int index){
        if(index == nums.length){ //边界
            ans.add(new ArrayList<Integer>(process));
            return;
        }
        //不选
        findSubsets(nums, index + 1);
        //选
        process.add(nums[index]); //本层逻辑
        findSubsets(nums, index + 1); //子问题
        process.remove(process.size() - 1); //还原现场
    }

    private List<List<Integer>> ans; //结果集
    private List<Integer> process; //过程结果集

    public static void main(String[] args) {
        Subsets subsets = new Subsets();
        int[] nums = {1, 2, 3};
        List<List<Integer>> ans = subsets.subsets(nums);
        for(List<Integer> process : ans){
            System.out.println(process);
        }
    }
}
